A typical high performance three dimensional graphics system will describe a surface to be rendered as surface patches defined by functions for each patch. Such functions might be, for example, nonuniform rational B-splines. The use of B-splines imposes certain limitations upon the edges of surface patches. Associated with B-spline functions is a normally rectangular uv parameter space. Parametric patch generation functions of u and v compute the values of the coordinates in XYZ space. The rectangular uv space limits the exactness with which the B-spline patch generation functions can represent surface patches having edges of certain shapes. For example, it is difficult to produce a good B-spline description for a patch that is a rectangular region with a circular portion removed from its interior. Either of the rectangular region or the circular portion by themselves would be practical, but their combination is too complex a primitive for a single unified B-spline description at the patch level. Subdividing the patch thwarts the motive for having patches in the first place. Trimming is a way to augment the B-spline description of the rectangular region with another one for the circular portion, and producing a hybrid surface patch in which one B-spline description "trims away" the surface described by another.
In the prior art, trimming has been performed by the software of the graphics system prior to the sending of device coordinates to the display hardware. Such trimming is necessarily a very complex task, and is generally too slow for use with moving images or interactive systems. It would be desirable to retain the use of B-splines and achieve the advantages offered by that technique of surface description, but at the same time allow high speed trimming.
According to a preferred method of the invention, trimming is performed on B-spline surface patch descriptions in a hardware graphics accelerator. It receives B-spline descriptions of the patch generation functions for the untrimmed patches and B-spline descriptions of trimming curves in the uv parameter space of the patch generation functions. The B-spline descriptions of the trimming curves are themselves functions of a parameter t. The graphics accelerator computes a sufficiently dense point by point representation of each trimming curve in uv space, in addition to point by point representations of the individual subspans in uv space whose associated polygons in XYZ space approximate the patch. The graphics accelerator determines where straight line approximating segments of the trimming curves cross subspan boundaries and changes the vertices of the subspans to trim away portions of the associated polygon. It does this by building a data structure of linked lists of vertex tables that represent the untrimmed polygon and any trimming curves that cut it. An appropriate traversal of the lists in the data structure produces a list of trimmed polygon vertices in device coordinates. That list may then be further processed to the pixel level by other hardware in the graphics accelerator.
Considerable attention is paid to avoiding the evils of roundoff error. A mechanism for describing where in a span a trimming curve is located allows the trimming operation to exclude from consideration those trimming curves that cannot possibly affect the polygon being processed. Another mechanism compensates for the effects of a non-ideal parameterization of the trimming curve functions, to prevent the production of an unnecessarily high number of polygon vertices. The trimming method is also compatible with recursive subdivision of patches to handle patches with a high number of trimming curves.